// but the glassy heart is born to be broken.
#include<bits/stdc++.h>
#define F(i, a, b) for(int (i)=(a);(i)<=(b);++(i))
#define dF(i, a, b) for(int (i)=(a);(i)>=(b);--(i))
#define mp make_pair
#define endl '\n'
#define ENDL putchar('\n')
#define forGraph(x) for(int i = head[x]; i; i = G[i].nxt)
#define pii pair<int, int>
#define pb push_back
using namespace std;

template<typename T>void read(T &x) {
    x = 0;
    char ch = getchar(); bool f = 0;
    while(!isdigit(ch)) {f |= (ch == '-'); ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + (ch - '0'); ch = getchar();}
    x = (f ? -x : x);
}

template<typename T>void write(T x) {
    if(x < 0) {putchar('-'); x = -x;}
    char _buf[70]; int p = 0;
    do{_buf[++p] = x % 10 + '0'; x /= 10;} while(x);
    do{putchar(_buf[p--]);} while(p);
}

const int N = 100 + 5, M = 1e6 + 5;

struct Graph{
    int to, w, nxt;
}G[M << 1];
int head[N], g_cnt;
void addEdge(int u, int v, int w = 1) {
    G[++g_cnt] = (Graph){v, w, head[u]}; head[u] = g_cnt;
}

int n, m, p, q, r;
int a[N], ans;
bool c[N];

void chkmax(int &x, int y) {
    x = x < y ? y : x;
}

int calc() {
    int cur = 0;
    F(i, 1, n) {
        dF(j, i - 1, 1) {
            if(c[i] == c[j] && a[i] == a[j]) {
                cur += a[i];
                break;
            }
        }
    }
    return cur;
}

void dfs(int now) {
    if(now == n + 1) {
        chkmax(ans, calc());
        return;
    }
    c[now] = 0;
    dfs(now + 1);
    c[now] = 1;
    dfs(now + 1);
}

void sol1() {
    dfs(1);
    cout << ans << '\n';
}

int dp[N][N][2];

int cal(int x, int y) {
    if(a[x] == a[y]) return a[x];
    return 0;
}

void sol2() {
    F(i, 1, n) dp[i][i][0] = dp[i][i][1] = -1e9;
    dp[1][1][0] = dp[1][1][1] = 0;
    F(i, 2, n) {
        dF(j, i, 1) {
            dF(k, j, 1) {
                dp[i][j][1] = max(dp[i][j][1], dp[j][k][1] + cal(i, j));
                chkmax(dp[i][j][1], dp[i][j][1] + dp[j - 1][k + 1][0]);
                dp[i][j][0] = max(dp[i][j][0], dp[j][k][0] + cal(i, j));
                chkmax(dp[i][j][0], dp[i][j][0] + dp[j - 1][k + 1][1]);
            }
            chkmax(ans, dp[i][j][1]);
            chkmax(ans, dp[i][j][0]);
        }
    }
    cout << dp[1][3][1] << endl;
    cout << ans << '\n';
}

void solve() {
    read(n); ans = 0;
    F(i, 1, n) read(a[i]);
    if(n <= 15) sol1();
    else sol2();
}

int T;

int main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    read(T);
    while(T--) {
        solve();
    }
}
